package com.mj.listen3.链表;

public class _0_环形单链表的约瑟夫问题 {
    public ListNode josephusKill1(ListNode head, int m) {
        if (head == null || head.next == head || m < 1) {
            return head;
        }

        // 使用last指针指向尾节点。因为要删除头节点的时候，直接用last.next = head.next就好了
        ListNode last = head;
        while (last.next != head) {
            // 一路找到尾节点
            last = last.next;
        }

        int count = 0;
        while (head != last) {
            if (++count == m) {
                // 删除此时的头节点
                last.next = head.next;
                count = 0;// 从新计数
            } else {
                // 转圈找节点
                last = last.next;
            }
            // 头永远指向 last 的next
            head = last.next;
        }// 退出while，此时的head和last相等，说明只剩下了一个节点了

        return head;
    }
}
